afl-lua

Fork of Lua adding AFL (https://github.com/google/afl) instrumentation to allow Lua scripts (not the VM itself) to be fuzzed.

1. Building
2. Try it out
3. C module fuzzing
4. Other Approaches
5. Advanced Usage
   • 5.1. Annotations
     • 5.1.1. Solving a Maze
     • 5.1.2. Obstacle Course
   • 5.2 Persistent Mode
   • 5.3 Dictionaries

1. Building

On Linux (maybe other POSIX-y systems?),

make

In the directory, there'll be an executable called "afl-lua".

2. Try it out

With afl-fuzz installed, make a test case called "test.lua" containing the following:

local function fuzz()
    local data = io.read("*all")
    if #data > 2 then
        local c = data:sub(1,1)
        local d = data:sub(2,2)
        local idx = tonumber(c)
        local idx2 = tonumber(d)
        local target = 50
        if idx and idx2 then
            for i = 1, idx*idx2 do
                if i == target then
                    if #data > 10 then
                        if data:sub(5,5) == 'f' then
                            if #data == 11 then
                                error('foo')
                            end
                        end
                    end
                end
            end
        end
    end
end

fuzz()

Run afl-fuzz with

mkdir {in, out}
echo foo > in/foo # just something to get the fuzzer corpus started
afl-fuzz -i in -o out ./afl-lua test.lua

You should see the fuzzer kick off and in short order find an input with will cause the script to exit on an error:

                       american fuzzy lop 2.52b (afl-lua)

┌─ process timing ─────────────────────────────────────┬─ overall results ─────┐
│        run time : 0 days, 0 hrs, 0 min, 22 sec       │  cycles done : 5      │
│   last new path : 0 days, 0 hrs, 0 min, 5 sec        │  total paths : 31     │
│ last uniq crash : 0 days, 0 hrs, 0 min, 4 sec        │ uniq crashes : 1      │
│  last uniq hang : none seen yet                      │   uniq hangs : 0      │
├─ cycle progress ────────────────────┬─ map coverage ─┴───────────────────────┤
│  now processing : 26* (83.87%)      │    map density : 0.06% / 0.22%         │
│ paths timed out : 0 (0.00%)         │ count coverage : 1.15 bits/tuple       │
├─ stage progress ────────────────────┼─ findings in depth ────────────────────┤
│  now trying : bitflip 4/1           │ favored paths : 7 (22.58%)             │
│ stage execs : 28/29 (96.55%)        │  new edges on : 11 (35.48%)            │
│ total execs : 107k                  │ total crashes : 12 (1 unique)          │
│  exec speed : 4704/sec              │  total tmouts : 0 (0 unique)           │
├─ fuzzing strategy yields ───────────┴───────────────┬─ path geometry ────────┤
│   bit flips : 1/920, 3/894, 4/813                   │    levels : 4          │
│  byte flips : 0/111, 0/86, 0/38                     │   pending : 6          │
│ arithmetics : 6/6184, 0/1022, 0/89                  │  pend fav : 0          │
│  known ints : 0/654, 0/2334, 0/1632                 │ own finds : 30         │
│  dictionary : 0/0, 0/0, 0/0                         │  imported : n/a        │
│       havoc : 16/77.0k, 1/15.0k                     │ stability : 100.00%    │
│        trim : 80.76%/65, 0.00%                      ├────────────────────────┘
└─────────────────────────────────────────────────────┘          [cpu000:  9%]

3. C module fuzzing

If C module dependencies are build with "afl-gcc", then coverage guidance from the C modules will be reported. This allows bugs in the C modules to found (which are more likely to be exploitable). With Luarocks, this is achieved by appending

CC=afl-gcc

when installing a rock e.g.

luarocks install foo CC=afl-gcc

An example of reproducing CVE-2018-11218 impacting version 0.4.0-0 of lua-cmsgpack is given which demonstrates how the fuzzing coverage extends across pure-Lua into C Lua modules.

4. Other Approaches

It's possible to make a fuzzer along the lines of afl-python where debug instrumentation is used to provide coverage guidance. See this gist for a Lua implementation.

5. Advanced Usage

5.1. Annotations

Fuzzing driven by code-coverage alone has limitations. Often, programs are structured so that a large proportion of code can be covered while reaching very few states. There comes a point where the fuzzer gets no useful feedback from coverage to guide future guesses and the fuzzer becomes no better than a dumb-fuzzer providing random inputs. It's possible to fuzz the tradionally unfuzzable by adding "human-in-the-loop" annotations to code, following the example of Ijon. Simple maze and obstacle course games are presented as examples of code where code coverage can be very quickly saturated without reaching any interesting states at all. By adding "annotations" to the code, the fuzzer can be guided to reach new and interesting states and be made to actually solve puzzles. This is quite remarkable as the maze, for example, is difficult enough to defeat symbolic exectution engines due to the explosion of states.

5.1.1. Solving a Maze

In ./examples/maze, a simple maze game is annotated with afl.map_set so that new player positions are reported back to the fuzzer, in addition to code coverage. This annotation allows the fuzzer to find inputs which solve the puzzle in a matter of minutes. Without this annotation, the fuzzer can be left for hours without success and it's unlikely that a good input would be found.

To try it out:

make # build afl-lua
cd examples/maze
./fuzz.sh

Here's a solution the fuzzer came up with after a few minutes:

5.1.2. Obstacle Course

Ijon modifies afl-fuzz to implement primitives IJON_MAX and IJON_MIN which can be used to make the fuzzer choose inputs which maximize or minimize a given state value, respectively. In afl-lua, equivalents are implemented without requiring changes to afl-fuzz. Instead, a table of previous max/min state values is stored by the annotation library and new values are communicated to afl-fuzz when those change.

To demonstrate this functionality, an obstacle course game is driven by afl-lua with a call to afl_max which prompts the fuzzer to choose inputs which maximise the distance to the right which the player travels.

To try it out:

make
cd examples/obstacle
./fuzz.sh

5.2. Persistent Mode

To improve peformance of fuzzing, persistent mode can be used. In this mode, the fuzzing process loops a configurable number of times without exiting while trying new inputs. This reduces the overhead of forking a new child process for every new input. The perfomance improvement can be around 3x but your milleage may vary.

The recipe is

for _ in afl.loop(1000) do
    local data = io.read("*all")
    local ok = pcall(target(data))
    if not ok then
        -- flag an interesting error to AFL
        os.exit(1)
    end
end

This may not be suitable for all targets. For example, if the target leaks memory, file descriptor etc, then this will result in resource exhaustion issues which are hard to debug. If the body of the loop keeps state between iterations, then the stability metric may fall and fuzzing will become ineffective.

5.3. Dictionaries

AFL can be configured to use a dictionary to guide fuzzing. To aid in creation of a dictionary, afl-lua has a mode where running a script will gather all strings involved in string comparisons. For example, the following target

local data = io.read("*all")
if data == "this is an example" then
    error('oops')
end

can be run so that strings are collected for a dictionary:

echo -n "foo" | AFL_TOKEN_FILE="$(pwd)/dictionary.txt" ./afl-lua -r test.lua

The content of dictionary.txt will be:

foo
this is an example

afl-fuzz will immediately find a input causing an error (as it's right there in the dictionary) when run with

afl-fuzz -x dictionary.txt -i in/ -o out/ ./afl-lua test.lua